package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了72.03%的用户
 */
func uniquePathsWithObstacles(obs [][]int) int {

	n, m := len(obs), len(obs[0])
	f := make([][]int, n)
	for i := 0; i < n; i++ { f[i] = make([]int, m) }

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if obs[i][j] == 1 { continue }

			if i == 0 && j == 0 {
				f[i][j] = 1
			} else {
				if i != 0 { f[i][j] += f[i - 1][j] }
				if j != 0 { f[i][j] += f[i][j - 1] }
			}
		}
	}

	return f[n - 1][m - 1]
}

func main() {

	obs := [][]int{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}
	fmt.Println(uniquePathsWithObstacles(obs))  // 2
}
